#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < (int)(b); ++i)
const int MOD = 1e9 + 7, SIG = 26, FF = 5, SZ = SIG * FF + 1;
typedef vector<ll> vl;
struct Mat {
  int r, c;
  vector<vl> f;
  Mat(int r, int c) : r(r), c(c), f(r, vl(c)){};
  Mat operator*(const Mat& b) const {
    Mat m(r, b.c);
    rep(i, 0, m.r) rep(j, 0, m.c) rep(k, 0, m.c) {
      (m.f[i][j] += f[i][k] * b.f[k][j] % MOD) %= MOD;
    }
    return m;
  }
  Mat pow(ll b) const {
    Mat m = *this, p = *this;
    for (--b; b; p = p * p, b >>= 1) {
      if (b & 1) m = m * p;
    }
    return m;
  }
};
int main() {
  Mat G(SZ, SZ);
  rep(i, 0, SIG) {
    rep(j, 0, SIG) G.f[i * FF][j * FF] = 1;
    rep(f, 0, FF - 1) G.f[i * FF + f + 1][i * FF + f] = 1;
  }
  int s = SIG;
  rep(i, 0, SIG) G.f[s * FF][i * FF] = 1;
  G.f[s * FF][s * FF] = 1;
  int n, m, ans = 0;
  cin >> n >> m;
  for (int i = 0, f; i < m; ++i) {
    char a, b;
    cin >> a >> b >> f;
    int i1 = (a - 'a') * FF, i2 = (b - 'a') * FF;
    G.f[i1][i2] = 0, G.f[i1][i2 + f - 1] = 1;
    G.f[i2][i1] = 0, G.f[i2][i1 + f - 1] = 1;
  }
  G = G.pow(n + 1);
  rep(i, 0, SIG)(ans += G.f[SIG * FF][i * FF]) %= MOD;
  cout << ans << endl;
}
